package day_2022_12_to_3.day;

/**
 * @author haomin
 * @date 2022/12/22 23:04
 **/
public class Day12_22_Num1799 {
    class Solution {
        public int maxScore(int[] nums) {
            int n = nums.length;

            int[][] gcdCache = new int[n][n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    gcdCache[i][j] = gcd(nums[i], nums[j]);
                }
            }
            int[] dp = new int[1 << n];
            int state = (1 << n) - 1;
            return help(nums, state, dp, 1, gcdCache);
        }

        // state >> i 是0，则代表第i位已删除
        // dp[state] = x
        public int help(int[] nums, int state, int[] dp, int base, int[][] gcdCache) {
            if (state == 0) {
                return 0;
            }
            if (dp[state] != 0) {
                return dp[state];
            }
            int n = nums.length;
            // 枚举所有此时可以删除的情况
            int ans = 0;
            for (int i = 0; i < n; i++) {
                if (!canUse(state, i)) continue;
                for (int j = i + 1; j < n; j++) {
                    if (!canUse(state, j)) continue;
                    int ns = state ^ (1 << i) ^ 1 << j;
                    ans = Math.max(ans, base * gcdCache[i][j] + help(nums, ns, dp, base + 1, gcdCache));
                }
            }

            dp[state] = ans;

            return ans;
        }

        public boolean canUse(int state, int i) {
            return ((state >> i) & 1) != 0;
        }

        public int gcd(int x, int y) {
            return y == 0 ? x : gcd(y, x % y);
        }
    }
}